package btree;

public class MyBtree {
    static class BTRNode {
        public int[] keys;// key数组
        public BTRNode[] subs;// 孩子数组
        public BTRNode parent;// 当前节点的父类
        int usedSize;// 当前节点存在key的有效个数
        public BTRNode() {
            // 这里我们实例化多分配了一个空间 是为了方便分裂
            this.keys = new int[M];
            this.subs = new BTRNode[M+1];
            usedSize = 0;
            parent = null;
        }
    }
    public BTRNode root; // 当前树的及诶单
    public static final int M = 3;// 当前树的孩子的数量
    public boolean insert(int key) {
        if(root == null) {
            // root == null 代表当前是第一次插入 直接赋值即可
            root = new BTRNode();
            root.keys[0] = key;
            root.usedSize++;
            return true;
        }
        // 如果不是头节点，不是首次插入，那就需要遍历整个树
        Pair<BTRNode,Integer> ret =  findNode(key);
        if(ret.getVal() != -1) {
            // 当前节点已经存在
            return false;
        }

        // 接下来就插入节点
        BTRNode cur = ret.getKey();
        int index = cur.usedSize -1;
        for(; index >= 0;index--) {
            if(key <= cur.keys[index]) {
                cur.keys[index + 1] = cur.keys[index];
            }else {
                // 已经到当前节点了
                break;
            }
        }
        // 当前i+1 已经到达要插入的节点了
        cur.keys[index+1] = key;
        cur.usedSize++;
        if(cur.usedSize < M) {
            // 插入成功 并且不满足分裂条件
            return true;
        }else {
            split(cur);
            return true;
        }
    }

    private void split(BTRNode cur) {
        BTRNode newNode = new BTRNode();
        int mid = cur.usedSize/2;
        int i = mid+1;
        int j = 0;
        for(;i<cur.usedSize;i++) {
            newNode.keys[j] = cur.keys[i];
            newNode.subs[j] = cur.subs[i];
            if(newNode.subs[j] != null) {
                newNode.subs[j].parent = cur;
            }
            j++;
        }
        // 多拷贝一次孩子
        newNode.subs[j] = cur.subs[i];
        if(newNode.subs[j] != null) {
            newNode.subs[j].parent = cur;
        }
        // 调整 newNode 和 cur 的有效个数
        newNode.usedSize = j;
        cur.usedSize = cur.usedSize - j - 1;
        // 更新当前节点的父节点
        BTRNode parent = cur.parent;
        if(parent == null) {
            // 表示当前是根节点分裂
            root = new BTRNode();
            root.keys[0] = cur.keys[mid];
            root.subs[0] = cur;
            cur.parent = root;
            root.subs[1] = newNode;
            newNode.parent = root;
            root.usedSize++;
            return;
        }

        // 在合适的位置插入父节点
        int endT = parent.usedSize - 1;
        int midVal = cur.keys[mid];

        for(;endT >= 0;endT--) {
            if(parent.keys[endT] >= midVal) {
                parent.keys[endT + 1] = parent.keys[endT];
                parent.subs[endT + 2] = parent.subs[endT +1];
            }else {
                break;
            }
        }
        parent.keys[endT + 1] = midVal;
        parent.subs[endT + 2] = newNode;
        parent.usedSize++;
        if(parent.usedSize >= M) {
            split(parent);
        }
    }

    private Pair<BTRNode,Integer> findNode(int key) {
        BTRNode cur = root;// 遍历root
        BTRNode parent = null;// 父亲节点
        while(cur != null) {
            int i =0;// i遍历下标
            while(i < cur.usedSize) {
                if(cur.keys[i] == key) {
                    return new Pair<>(cur,i);
                }else if(cur.keys[i] < key) {
                    i++;
                }else {
                    break;
                }
            }
            parent = cur;
            cur = cur.subs[i];
        }
        return new Pair<>(parent,-1);
    }
    public void inorder(BTRNode root){
        if(root == null)
            return;
        for(int i = 0; i < root.usedSize; ++i){
            inorder(root.subs[i]);
            System.out.println(root.keys[i]);
        }
        inorder(root.subs[root.usedSize]);
    }
}
